package com.lw.leetcode.greedy.c;

import com.lw.test.util.Utils;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * 2472. 不重叠回文子字符串的最大数目
 *
 * @author liw
 * @version 1.0
 * @date 2022/11/15 9:24
 */
public class MaxPalindromes {

    public static void main(String[] args) {
        MaxPalindromes test = new MaxPalindromes();

        // 2
//        String str = "abaccdbbd";
//        int k = 3;

        // 0
//        String str = "adbcda";
//        int k = 2;

        //
        String str = Utils.getStr(2000, 'a', 'z');
        int k = 2;
        System.out.println();

        int i = test.maxPalindromes(str, k);
        System.out.println(i);
    }

    public int maxPalindromes(String s, int k) {
        int length = s.length();
        char[] chars = s.toCharArray();
        int[][] arr = new int[length][length];
        arr[length - 1][length - 1] = 1;
        for (int i = length - 2; i >= 0; i--) {
            arr[i][i] = 1;
            char a = chars[i];
            if (a == chars[i + 1]) {
                arr[i][i + 1] = 1;
            }
            for (int j = i + 2; j < length; j++) {
                if (a == chars[j]) {
                    arr[i][j] = arr[i + 1][j - 1] > 0 ? 1 : 0;
                }
            }
        }
        List<Long> list = new ArrayList<>();
        for (int i = 0; i < length; i++) {
            for (int j = i + k - 1; j < length; j++) {
                if (arr[i][j] > 0) {
                    list.add(((long) i << 32) + j);
                }
            }
        }
        Collections.sort(list);
        int count = 0;
        int item = -1;
        for (long aLong : list) {
            int a = (int) (aLong >> 32);
            int b = (int) aLong;
            if (a > item) {
                count++;
                item = b;
            } else {
                item = Math.min(item, b);
            }
        }
        return count;
    }

}
